2588. Симметрия

Фермер Джон, которому нравится симметрия, занят сейчас размещением своих коров на поле размером n * m.

Для сохранения симметрии Фермер Джон располагает коров в следующем порядке. Он ставит корову в самом центре поля. Если такого квадрата нет, то он просто останавливается. Затем он разбивает поле на четыре одинаковых по размеру меньших полей (разделенных строками и столбцами с коровою в центре) и размещает коров на каждой из этих областей по описанному алгоритму. Джон продолжает деление меньших полей до тех пор, пока это можно совершить, либо пока поле имеет центральную клетку.

Рассмотрим пример. Если n = 7 и m = 15, то фермер Джон размещает корову в строке 4 и колонке 8 и делит поле на четыре поля размером 3 * 7. В каждом из 3 * 7 полей Фермер Джон располагает корову в строке 2 и колонке 4, и снова делит каждое из них на четыре 1 * 3 поля. Процесс показан ниже (через C обозначена корова):

21 корова требуется для указанной схемы расположения. Если например n = m = 5, то Фермеру Джону достаточно одной коровы, так как после разделения поле 2 * 2 не будет иметь центральной клетки. Помогите Фермеру Джону определить количество коров, необходимое для расположения описанным образом на поле.

Вход. Два числа n и m (1 ≤ n ≤ 10⁹, 1 ≤ m ≤ 10⁹).

Выход. Выведите требуемое количество коров.

Пример входа	Пример выхода
7 15	21

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Пусть f(n, m) – количество коров, которое можно разместить на поле размером n * m. Если n или m четно, то поле центра не имеет, поэтому на нем невозможно разместить ни одной коровы. В этом случае f(n, m) = 0.

Если n и m нечетны, то в центре ставим одну корову и далее рекурсивно расставляем коров в четырех полях размером n / 2 * m / 2:

f(n, m) = 1 + 4 * f(n / 2, m / 2)

Пример

Вычислим ответ для заданного теста.

f(7, 15) = 1 + 4 * f(3, 7) = 21

f(3, 7) = 1 + 4 * f(1, 3) = 5

f(1, 3) = 1 + 4 * f(0, 1) = 1

Реализация алгоритма

Функция f возвращает количество коров, которое можно разместить на поле размером n * m.

long long f(int n, int m)

{

if (n % 2 == 0 || m % 2 == 0) return 0;

return 1 + 4 * f(n / 2, m / 2);

}

Основная часть программы. Читаем входные данные. Вычисляем и выводим ответ.

scanf("%d %d", &n, &m);

res = f(n, m);

printf("%lld\n", res);

Java реализация

import java.util.*;

public class Main

{

static long f(int n, int m)

{

if (n % 2 == 0 || m % 2 == 0) return 0;

return 1 + 4 * f(n/2, m/2);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

long res = f(n, m);

System.out.println(res);

}

}

Python реализация

def f(n, m):

if n % 2 == 0 or m % 2 == 0: return 0

return 1 + 4 * f(n // 2, m // 2)

n, m = map(int,input().split())

res = f(n, m);

print(res)